package 常见算法.分治之归并排序;

/**
 * @Date 2024/6/14 21:00
 * @description: 实现归并排序
 * .            https://leetcode.cn/problems/sort-an-array/
 * @Author LittleNight
 */
public class likou912 {

    int[] tmp; // 定义一个辅助数组

    // 归并排序练习 (验证已对)
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        mergeSort5(0, n - 1, nums);
        return nums;
    }

    // 升序
    private void mergeSort5(int left, int right, int[] nums) {
        // 递归出口, 说明没有区间
        if(left >= right) return;

        // 先分区间排序, 然后合并两个有序数组
        // 1. 分区间排序
        int mid = (left + right) / 2;
        // [left, mid]  [mid + 1,  right]
        mergeSort5(left, mid, nums);
        mergeSort5(mid + 1, right, nums);

        // 2. 合并两个有序数组
        // [left, mid]  [mid + 1,  right]
        // cur1 遍历 [left, mid] 这个区间
        // cur2 遍历 [mid + 1, right] 这个区间
        // i 遍历 tmp 辅助数组
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right) {
            // 升序: 先排小的
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        // 3. 处理还没有排完的元素
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        // 4. 拷贝辅助数组元素到原数组中.
        // 原数组区间 [left, right]
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }
    }


    public int[] sortArray1(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        mergeSort4(0, n - 1, nums);
        return nums;
    }

    private void mergeSort4(int left, int right, int[] nums) {
        // 区间内只有一个元素或者元素不存在， 那么直接返回没有排序的必要
        if(left >= right) return;

        // 归并排序的主逻辑过程
        // 1. 找到一个中间位置
        int mid = (left + right) / 2;
        // [left, mid] [mid + 1, right]

        // 2. 先进行左右两边的分割，排个序
        mergeSort4(left, mid, nums);
        mergeSort4(mid + 1, right, nums);

        // 3. 两边排好序之后， 合并有序数组。（核心操作）
        // cur1 遍历 [left, mid] 这个区间
        // cur2 遍历 [mid + 1, right] 这个区间
        // i 遍历 tmp 辅助数组
        int cur1 = left, cur2 = mid + 1, i = 0;
        // while(cur1 <= left && cur2 <= right) {
        while(cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        // 4.处理cur1 或者 cur2 还没有遍历完的数组
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        // 5. 把辅助数组中的数组拷贝到原数组中
        // j 遍历的是原数组， nums中的 【left, right】 这个区间
        for (int j = left; j <= right; j++) {
            // tmp 要从 0 开始遍历
            nums[j] = tmp[j - left];
        }
    }
}
